﻿
namespace TIKSN.StringSearchingAlgorithms
{
    public class LongestCommonSubsequence : ITextComparer
    {
        public int Compare(string s1, string s2)
        {
            int n1 = s1.Length + 1;
            int n2 = s2.Length + 1;

            int[,] matrix = this.GetMatrix(s1, s2);

            return matrix[n1 - 1, n2 - 1];
        }

        public int[,] GetMatrix(string s1, string s2)
        {
            int n1 = s1.Length + 1;
            int n2 = s2.Length + 1;

            int[,] matrix = new int[n1, n2];

#if DEBUG
            for (int i = 0; i < n1; i++)
            {
                System.Diagnostics.Debug.Assert(matrix[i, 0] == 0);
            }

            for (int i = 0; i < n2; i++)
            {
                System.Diagnostics.Debug.Assert(matrix[0, i] == 0);
            }
#endif
            for (int i1 = 1; i1 < n1; i1++)
            {
                for (int i2 = 1; i2 < n2; i2++)
                {
                    string c1 = s1.Substring(i1 - 1, 1);
                    string c2 = s2.Substring(i2 - 1, 1);

                    if (string.Compare(c1, c2, System.Globalization.CultureInfo.InvariantCulture, System.Globalization.CompareOptions.IgnoreCase) == 0)
                    {
                        matrix[i1, i2] = matrix[i1 - 1, i2 - 1] + 1;
                    }
                    else
                    {
                        matrix[i1, i2] = System.Math.Max(matrix[i1 - 1, i2], matrix[i1, i2 - 1]);
                    }
                }
            }

            return matrix;
        }
    }
}
